package array;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

public class FindMinArrowShots452 {

    @Test
    public void test() {
        findMinArrowShots(new int[][]{new int[]{10,16}, new int[]{2,8}, new int[]{1,6}, new int[]{7,12}});
        findMinArrowShots(new int[][]{new int[]{1,2}, new int[]{3,4}, new int[]{5,6}, new int[]{7,8}});
        findMinArrowShots(new int[][]{new int[]{1,2}, new int[]{2,3}, new int[]{3,4}, new int[]{4,5}});
        findMinArrowShots(new int[][]{new int[]{2,3}, new int[]{2,3}});
        findMinArrowShots(new int[][]{new int[]{-2147483648,2147483647}});
        findMinArrowShots(new int[][]{new int[]{-2147483646,-2147483645}, new int[]{2147483646,2147483647}});
    }

    // 反过来想, 不相交的区间一定要用不同的剑射中, 与435相似.
    // 但是, 如果A与B和C都相交, 不想交集合中有A, 能保证射中A时, 就能同时将B和C也射中吗?
    // 答案可以的, 因为是按右边界排序的, 射A最右边界, 一定能将与A相交的都射中.
    // 另外, 注意擦边的也算.
    public int findMinArrowShots(int[][] v) {
        Arrays.sort(v, new IntervalComparator());
        long lastEnd = Long.MIN_VALUE;
        int individuals = 0;
        for (int i = 0; i < v.length; i++) {
            if ((long)v[i][0] > lastEnd) {
                individuals++;
                lastEnd = v[i][1];
            }
        }
        System.out.format("intervals: %s, individuls: %d\n", Arrays.toString(v), individuals);
        return individuals;
    }

    static class IntervalComparator implements Comparator<int[]> {
        @Override
        public int compare(int[] a, int[] b) {
            return Long.compare((long)a[1] - (long)b[1], 0L);
        }
    }
}
